// Author:
//  ChungChe Hsieh 2011/07/26
//
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <unistd.h>

int bb[10]={0}; // content: 0~20
int rr[10]={0}; // real data
int vb[10];
int holes[10]={0};

int currMaxHeight=0;
int currMin;
int currDiff[4]={99,99,99,99};

void init()
{
    memset(bb, 0, sizeof(bb));
    memset(rr, 0, sizeof(rr));
    memset(vb, 0, sizeof(vb));
    memset(holes, 0, sizeof(holes));
    
    currMaxHeight=0;
    currMin = 0;
    memset(currDiff, 0, sizeof(currDiff));
}
//int dd[9]={0}; // difference, no first element
//
//      7 difference shape, each shape have most 4 config
//      shape     color        config_num 
//    ====================================
//       000      UNDEFINED        0
//       001      light blue       2
//       010      yellow           1
//       011      orange           4
//       100      blue             4
//       101      green            2
//       110      red              2
//       111      pink             4
//    ====================================
//       Config
//    ====================================
enum{
    S_UNKNOWN,
    S_LIGHT_BLUE,
    S_YELLOW,
    S_ORANGE,
    S_BLUE,
    S_GREEN,
    S_RED,
    S_PINK,

};
#if 0
enum {
    G_HOLE = -8,
    G_ADDHEIGHT = -6,
    G_EXISTHOLES = -3,
    G_ELIMI = 8,
};
#endif
int G_HOLE = -8;
int G_ADDHEIGHT = -8;
int G_EXISTHOLES = -4;
int G_ELIMI = 20;
int G_FLAT = 2;

int elimiFlag=0;

// 1: shape 2: config 3: data
struct sol
{
    int shape; // which shape
    int config; // which config
    int pos; // where should I place
    int diff[4];
    int elimi;
};
const int seq[7][4][3]={
    { {0, 0, 0}, {-9,-9,-9}, {-9,-9,-9}, {-9,-9,-9} },
    { {0,-9,-9}, {-9,-9,-9}, {-9,-9,-9}, {-9,-9,-9} },
    { {0, 0,-9}, { 0,-9,-9}, {-1, 0,-9}, { 2,-9,-9} },
    { {0, 0,-9}, {-2,-9,-9}, { 0, 1,-9}, { 0,-9,-9} },
    { {0,-1,-9}, { 1,-9,-9}, {-9,-9,-9}, {-9,-9,-9} },
    { {1, 0,-9}, {-1,-9,-9}, {-9,-9,-9}, {-9,-9,-9} },
    { {0, 0,-9}, {-1,-9,-9}, { 1,-1,-9}, { 1,-9,-9} },
};
const int hh[7][4][4]={
    { { 1, 1, 1, 1}, { 4,-9,-9,-9}, {-9,-9,-9,-9}, {-9,-9,-9,-9} },
    { { 2, 2,-9,-9}, {-9,-9,-9,-9}, {-9,-9,-9,-9}, {-9,-9,-9,-9} },
    { { 2, 2, 2,-9}, { 3, 3,-9,-9}, { 2, 1, 1,-9}, { 1, 3,-9,-9} },
    { { 2, 2, 2,-9}, { 3, 1,-9,-9}, { 1, 1, 2,-9}, { 3, 3,-9,-9} },
    { { 2, 2, 1,-9}, { 2, 3,-9,-9}, {-9,-9,-9,-9}, {-9,-9,-9,-9} },
    { { 1, 2, 2,-9}, { 3, 2,-9,-9}, {-9,-9,-9,-9}, {-9,-9,-9,-9} },
    { { 2, 2, 2,-9}, { 3, 2,-9,-9}, { 1, 2, 1,-9}, { 2, 3,-9,-9} },
};
const int rh[7][4][4]={
    { { 1, 1, 1, 1}, { 4,-9,-9,-9}, {-9,-9,-9,-9}, {-9,-9,-9,-9} },
    { { 2, 2,-9,-9}, {-9,-9,-9,-9}, {-9,-9,-9,-9}, {-9,-9,-9,-9} },
    { { 1, 1, 2,-9}, { 3, 1,-9,-9}, { 2, 1, 1,-9}, { 1, 3,-9,-9} },
    { { 2, 1, 1,-9}, { 3, 1,-9,-9}, { 1, 1, 2,-9}, { 1, 3,-9,-9} },
    { { 1, 2, 1,-9}, { 2, 2,-9,-9}, {-9,-9,-9,-9}, {-9,-9,-9,-9} },
    { { 1, 2, 1,-9}, { 2, 2,-9,-9}, {-9,-9,-9,-9}, {-9,-9,-9,-9} },
    { { 1, 2, 1,-9}, { 3, 1,-9,-9}, { 1, 2, 1,-9}, { 1, 3,-9,-9} },
};
const int ww[7][4]={
    {4,1,0,0},
    {2,0,0,0},
    {3,2,3,2},
    {3,2,3,2},
    {3,2,0,0},
    {3,2,0,0},
    {3,2,3,2},
};
const int wh[7][4]={
    {1,4,0,0},
    {2,0,0,0},
    {2,3,2,3},
    {2,3,2,3},
    {2,3,0,0},
    {2,3,0,0},
    {2,3,2,3},
};
// ----------------------------------------------------------
// light blue                     @
//                                @
//    @@@@                        @
//                                @
//
// height   1  1  1  1            4
// ----------------------------------------------------------
// yellow
//
//    @@
//    @@
//
// height   2  2
// ----------------------------------------------------------
// orange
//                        @                       @@                           
//     @                  @           @@@          @                                            
//   @@@                  @@          @            @                                                       
//                                                                              
// height   1  1  2       3  1        2  2  2     3  3                                                 
// ----------------------------------------------------------
// blue
//                        @@                      @ 
//   @                    @           @@@         @ 
//   @@@                  @             @        @@
//  
// height   2  1  1       3  3        2 2 2      1  3
// ----------------------------------------------------------
// green
//                          @
//    @@                    @@
//   @@                      @
// 
// height   1  2  2         3 2
// ----------------------------------------------------------
// red
//                           @
//   @@                     @@
//    @@                    @
//
// height   2  2  1         2  3
// ----------------------------------------------------------
// pink
//                      @                        @                        
//    @                 @@          @@@         @@                                     
//   @@@                @            @           @                                         
//
// height   1  2  1     3  2        2  2  2     2 3
// ----------------------------------------------------------
//
int random_pick()
{
    return rand()%7+1;
}
int get_width(int shape, int config)
{
    return ww[shape-1][config];
}
void set_CurrMin(int min)
{
    currMin = min;
}
void set_CurrDiff(int *v)
{
    currDiff[0]=v[0];
    currDiff[1]=v[1];
    currDiff[2]=v[2];
    currDiff[3]=v[3];
}
// put shape on it
void set_rr(int idx, int holeNum, int realH)
{
    int i;
    int currH = bb[idx];
    //int value = holeNum+realH;
    int data=0;
    for(i=0;i<realH;++i)
    {
        data |= (1 << i);
    }
    data = data << (holeNum+currH);
    rr[idx] |= data;
}
#if 0
void set_vb(int idx, int holeNum, int realH)
{
    int i;
    int value = holeNum+realH;
    int data=0;
    for(i=0;i<realH;++i)
    {
        data |= (1 << i);
    }
    data = data << (holeNum);
    vb[idx] |= data;
}
#endif
//void set_vb(int idx, int holeNum, int realH, int lv)
void set_vb(int idx, int holeNum, int realH)
{
    int i;
    int currH = bb[idx];
    //int value = holeNum+realH;

    int data=0;
    for(i=0;i<realH;++i)
    {
        data |= (1 << i);
    }
    data = data << (holeNum+currH);
    vb[idx] |= data;
    //vb[idx] = (vb[idx] >> lv);
}
void check_elimi()
{
}
void print_shape(int shape, int rotate)
{
    printf("curr shape=\n");
    switch(shape)
    {
        case S_UNKNOWN:
            printf("UNKNOW\n");
            break;
        case S_LIGHT_BLUE:
            if(!rotate)
                printf("@\n@\n@\n@\n");
            else
                printf("@@@@\n");
            break;
        case S_YELLOW:
            printf("@@\n@@\n");
            break;
        case S_ORANGE:
            switch(rotate)
            {
                case 3:
                    printf("  @\n@@@\n");
                break;
                case 0:
                    printf("@ \n@ \n@@\n");
                break;
                case 1:
                    printf("@@@\n@\n");
                break;
                case 2:
                    printf("@@\n @\n @\n");
                break;
            }
            break;
        case S_BLUE:
            switch(rotate)
            {
                case 3:
                    printf("@  \n@@@\n");
                break;
                case 0:
                    printf("@@\n@ \n@ \n");
                break;
                case 1:
                    printf("@@@\n  @\n");
                break;
                case 2:
                    printf(" @\n @\n@@\n");
                break;
            }
            break;
        case S_GREEN:
            if(!rotate)
                printf("@ \n@@\n @\n");
            else
                printf(" @@\n@@\n");
            break;
        case S_RED:
            if(!rotate)
                printf(" @\n@@\n@ \n");
            else
                printf("@@ \n @@\n");
            break;
        case S_PINK:
            switch(rotate)
            {
                case 1:
                    printf(" @ \n@@@\n");
                break;
                case 0:
                    printf("@\n@@\n@\n");
                break;
                case 3:
                    printf("@@@\n @ \n");
                break;
                case 2:
                    printf(" @\n@@\n @\n");
                break;
            }
            
            break;
    };
}
// return the cost when I put this shit on somewhere
// Grading policy
// Holes  : -3
// Add Height : -1
// Can elimi : 8
int grading(int shape, int config, int pos)
{
    int score = 0;
    int w=get_width( shape, config );
    int i, j;
    int min=32; // also add to score the more min it has, the better score it will get
    int diff[4]={64,64,64,64};
    int afterPlace[4]={-99,-99,-99,-99};
    int low_pos;
    for(i=0;i<w;++i)
    {
        if(pos+i>9)
            printf("%s %d error!\n",__func__,__LINE__);
        int h=hh[shape-1][config][i];
        diff[i] = (20-h)-bb[pos+i];
        if( diff[i] < min )
        {
            min = diff[i];
            low_pos = i;
        }
    }
    set_CurrMin( min );
    //score+=(min+1)/2;
    score+=(min+1)*G_FLAT;
    for(i=0;i<w;++i)
        diff[i]-=min;
    set_CurrDiff( &diff[0] );
    // calculate holes
    int holeNum=0;
    for(i=0;i<w;++i)
        holeNum+=diff[i];
    score+=holeNum*G_HOLE;
    // calculate new height, and max height
    int maxHeight = -999;
    for(i=0;i<w;++i)
    {
        afterPlace[i]=diff[i]+rh[shape-1][config][i];
        if( afterPlace[i] > maxHeight )
            maxHeight = afterPlace[i];
    }
    // check the diff with currMaxHeight
    int addHeight = maxHeight - currMaxHeight;
    if( addHeight < 0 ) addHeight = 0;
    score+=addHeight*G_ADDHEIGHT;
    // check exist holes
    for(i=0;i<w;++i)
    {
        if(pos+i>9)
            printf("%s %d error!\n",__func__,__LINE__);
        score+=(holes[pos+i]*G_EXISTHOLES);
    }
    // check elimi
    //  find lowest bb
    int lowestBB=99999;
    for(i=0;i<w;++i)
    {
        if(pos+i>9)
            printf("%s %d error!\n",__func__,__LINE__);
        if(20-min-hh[shape-1][config][i]< lowestBB )
            lowestBB = 20-min-hh[shape-1][config][i];
    }
    //printf("pos=%d config=%d lowestBB=%d\n",pos, config, lowestBB );
    for(i=0;i<10;++i)
    {
        vb[i]=rr[i];
    }
    
    for(i=0;i<w;++i)
    {
        set_vb(pos+i, diff[i], rh[shape-1][config][i]);
        //set_vb(pos+i, diff[i], rh[shape-1][config][i], lowestBB);
        if(pos+i>9)
            printf("%s %d error!\n",__func__,__LINE__);
    }
    for(i=0;i<10;++i)
    {
        vb[i]>>=lowestBB;
    }
    elimiFlag = 0; 
    //for(i=0;i<lowestBB;++i)
    for(i=0;i<wh[shape-1][config];++i)
    {
        int sum=0;
        int combo_count=0;
        for(j=0;j<10;++j)
        {
            if(vb[j] & (1<<i) )
                sum++;
        }
        if(sum == 10 )
        {
            combo_count++;
            printf("!!!!!! elimi shape=%d config=%d pos=%d\n", shape, config, pos);
            print_shape( shape, config);
            score += G_ELIMI*combo_count;
            
            elimiFlag |= (1<< (i+lowestBB));
            printf("elimiFlag=%d\n", elimiFlag );
        }
    }
    return score;
}
struct sol get_sol( int shape )
{
    int i,j, width;
    int score, maxScore = -9999999;

    struct sol best_sol;
    best_sol.shape = shape;
    best_sol.config = 0;
    best_sol.pos = 0;
    best_sol.diff[0] = currDiff[0];
    best_sol.diff[1] = currDiff[1];
    best_sol.diff[2] = currDiff[2];
    best_sol.diff[3] = currDiff[3];
    best_sol.elimi = 0;
    // for each rotation(config)
    for(i=0;i<4;++i)
    {
        if(hh[shape-1][i][0]==-9)
            break;
        width = get_width( shape, i );
        if( !width )
            continue;
        width = 10 - width+1;
        // for each position
        for(j=0;j< width;++j)
        {
            //printf("config=%d pos=%d\n", i,j);
            score = grading( shape, i, j );
            //printf("score=%d\n",score);
            if( score > maxScore )
            {
                maxScore = score;
                best_sol.shape = shape;
                best_sol.config = i;
                best_sol.pos = j;
                
                best_sol.diff[0] = currDiff[0];
                best_sol.diff[1] = currDiff[1];
                best_sol.diff[2] = currDiff[2];
                best_sol.diff[3] = currDiff[3];

                best_sol.elimi = elimiFlag;
            }
        }
        //printf("=========================\n");
    }
    printf("rotate time=%d\n", best_sol.config);
    printf("best pos=%d\n", best_sol.pos);
    return best_sol;
}
void print_text(int shape)
{
    printf("curr shape=");
    switch(shape)
    {
        case S_UNKNOWN:
            printf("Unknown\n");
            break;
        case S_LIGHT_BLUE:
            printf("Light blue\n");
            break;
        case S_YELLOW:
            printf("Yellow\n");
            break;
        case S_ORANGE:
            printf("Orange\n");
            break;
        case S_BLUE:
            printf("Blue\n");
            break;
        case S_GREEN:
            printf("Green\n");
            break;
        case S_RED:
            printf("Red\n");
            break;
        case S_PINK:
            printf("Pink\n");
            break;
    };
}
void print_bb()
{
    int i,j;
    for(i=0;i<10;++i)
    {
        int size=bb[i];
        printf("(%02d)|", size);
        for(j=0;j<size;++j)
            printf("@");
        printf("\n");
    }
    printf("\n");
}
void print_rr()
{
    int i,j;
    for(i=0;i<10;++i)
    {
        int size=bb[i];
        printf("%d|(%02d)|(%4d)|", holes[i], size, rr[i]);
        for(j=0;j<20;++j)
        {
            if(rr[i] & (1<<j))
                printf("@");
            else
                printf(" ");
        }
        printf("\n");
    }
    printf("\n");
}
void print_vb()
{
    int i,j;
    for(i=0;i<10;++i)
    {
        int size=bb[i];
        printf("%d|(%02d)|", holes[i], size);
        for(j=0;j<20;++j)
        {
            if(vb[i] & (1<<j))
                printf("@");
            else
                printf(" ");
        }
        printf("\n");
    }
    printf("\n");
}

int update_rr( int value, int idx)
{
    int a = (1 << idx ) - 1;
    int partA = value & a;
    int partB = ((value >> 1) >> idx ) << idx;
    
    return partA+partB;
}
void elimi_row( int row )
{
    int i;
    for(i=0;i<10;++i)
    {
        rr[i] = update_rr(rr[i], row);
    }
}
void dec_bb()
{
    int i,j;
    int value;
    int maxB=0;
    for(i=0;i<10;++i)
    {
        value=rr[i];
        if(value == 0)
        {
            bb[i] = 0;
            continue;
        }
        for(j=0;j<20;++j)
        {
            if(value&1)
            {
                maxB=j+1;
            }
            value>>=1;
        }
        bb[i]=maxB;
    }
        //bb[i]--;
}
void update_holes()
{
    int i,j;
    for(i=0;i<10;++i)
    {
        int hol=0;
        for(j=0;j<bb[i]-1;++j)
        {
            if( ( rr[i] & (1<< j) ) == 0 )
            {
                printf("holes found at (%d,%d) rr[%d]=%d\n", i, j, i,rr[i]);
                hol++;
            }
        }
        holes[i]=hol;
    }
}

void is_sol_elimi( struct sol solution )
{
    int i;
    //for(i=0;i<20;++i)
    for(i=19;i>=0;--i)
    {
        if(solution.elimi & (1<<i))
        {
            elimi_row( i );
            currMaxHeight--;
            dec_bb(); 
            update_holes();
        }
    }
}
void update_bb( struct sol solution)
{
    //print_rr();
    int i;//,j;
    int shape = solution.shape;
    int config = solution.config;
    int pos = solution.pos;
    int w = get_width( shape, config );
    int maxH = -99999;
    for(i=0;i<w;++i)
    {
        if(pos+i>9)
            printf("%s %d error!\n",__func__,__LINE__);
        holes[pos+i]+=solution.diff[i];
        set_rr(pos+i, solution.diff[i], rh[shape-1][config][i]);
        bb[pos+i]+=rh[shape-1][config][i]+solution.diff[i];
        

        if(bb[pos+i] > maxH )
            maxH = bb[pos+i];
    }
    // update currMaxHeight
    if( maxH > currMaxHeight )
        currMaxHeight = maxH; 
    is_sol_elimi( solution);
    //print_bb();
    print_rr();
    //printf("------\n");
    //print_vb();
}
void pick_and_place()
{
    struct sol solution;
    // 1. Random pick a shape (% 7 + 1)
    int s = random_pick();
    //print_shape( s );
    // 2. Which shape is it, rotate all ,scan all dd[], find the best choice(grading)
    solution = get_sol(s);
    print_shape( solution.shape, solution.config);
    // 3. Update bb[] and dd[]
    update_bb( solution );
    
}
int run(int hole, int add, int existhole, int elimi, int flat)
{
    int count=0;
    G_HOLE = hole,
    G_ADDHEIGHT = add,
    G_EXISTHOLES = existhole,
    G_ELIMI = elimi,
    G_FLAT = flat;
    init();
    srand( time(NULL) );
    while(currMaxHeight<20)
    {
        pick_and_place();
        count++;
//        usleep(1000000);
        if(count==8000)
            break;
    }
    //fprintf(stderr,"die at %d\n",count);
    return count;
}
int main(int argc, char *argv[])
{
    // teris 
    //run(-8,-6,-3,16);
    //run(-8,-8,-6,20,2);
    
    // try to find best config value
    int a=-1, b=-1, c=-1, d=-1, e=-1;
    int i, j, k, l, m;
    int best_count = -999;
    int value;
    int percent=0;
    for(i=0;i<20;++i)
    {
        fprintf(stderr,"%d %%\n", percent);
        for(j=0;j<20;j++)
        {
            for(k=0;k<20;k++)
            {
                for(l=0;l<20;l++)
                {
                    for(m=0;m<20;m++)
                    {
                        value=run(-1*i,-1*j,-1*k,l,m);
                        if(value > best_count)
                        {
                            best_count = value;
                            a = i;
                            b = j;
                            c = k;
                            d = l;
                            e = m;
    fprintf(stderr,"(%d,%d,%d,%d,%d) = %d\n", a, b, c, d, e, value);
                        }
                    }
                }
            }
        }
        percent+=5;

    }
    fprintf(stderr,"(%d,%d,%d,%d,%d)\n", a, b, c, d, e);
    return 0;
}
